{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. 画图解释图像卷积滤波的基本原理，并进一步简述常见的图像平滑滤波算法。\n",
    "    \n",
    "    1. 图像卷积滤波的基本原理:\n",
    "    \n",
    "        图像滤波的卷积定义\n",
    "        $${f(x,y)}*{g(x,y)}= {\\frac{1}{NM}}{\\sum^{N-1}_{n=0}}{\\sum^{M-1}_{m=0}}{f(x+n,y+m)g(n,m)}$$  \n",
    "        \n",
    "        图像滤波的基本原理\n",
    "        ![像素卷积滤波计算](01.png)\n",
    "        \n",
    "        对于N * M的卷积核，通常N和M取奇数，这样卷积核有一个中心点，这里以3 * 3的卷积和为例，上图中卷积核为:\n",
    "        $$ \\left[ \\begin{matrix} -4 & 0 & 0 \\\\ 0 & 0 & 0 \\\\ 0 & 0 & 4 \\end{matrix} \\right] $$ \n",
    "        相关模板为\n",
    "        $$ \\left[ \\begin{matrix} 4 & 0 & 0 \\\\ 0 & 0 & 0 \\\\ 0 & 0 & -4 \\end{matrix} \\right] $$ \n",
    "        一个像素点的滤波计算方法是将模板的中心点与该像素对齐后，将模板中各点的值与图像中对应的点值相乘，然后再将所得的积累加，最后所得的和作为该像素的滤波结果；\n",
    "        \n",
    "        这样做就将一个像素的滤波值与其周围的像素关联起来；  \n",
    "        如果不对图像进行扩展，图像边缘的像素无法计算滤波值，导致滤波后的图像x方向少N-1个像素，y方向少M-1个像素；\n",
    "        \n",
    "    2. 常见的图像平滑滤波算法:\n",
    "    \n",
    "        1. 平均滤波\n",
    "        \n",
    "            取一个小区域内像素的平均值，通常取3 * 3的区域，利用卷积滤波计算，根据选择参与计算平均值得点不同可以有多种不同的卷积核，例如：\n",
    "            1. 所有点都参与平均值计算：\n",
    "                $$ {\\frac{1}{9}} \\left[ \\begin{matrix} 1 & 1 & 1 \\\\ 1 & 1 & 1 \\\\ 1 & 1 & 1 \\end{matrix} \\right] $$ \n",
    "            2. 像素自身和其上下左右的四个点进行平均计算：\n",
    "                $$ {\\frac{1}{5}} \\left[ \\begin{matrix} 0 & 1 & 0 \\\\ 1 & 1 & 1 \\\\ 0 & 1 & 0 \\end{matrix} \\right] $$ \n",
    "            3. 像素周围的8个点参与计算但像素本身不参与：\n",
    "                $$ {\\frac{1}{8}} \\left[ \\begin{matrix} 1 & 1 & 1 \\\\ 1 & 0 & 1 \\\\ 1 & 1 & 1 \\end{matrix} \\right] $$ \n",
    "                \n",
    "        2. 加权平均滤波\n",
    "        \n",
    "            与平均滤波类似，但考虑不同位置的邻点与滤波像素的相关性不同，为其赋予不同的权值，表达其对滤波的影响，无论如何设置权值，其权值和应为1，例如：\n",
    "            1. 中心点的权值是其他点的二倍：\n",
    "                $$ {\\frac{1}{10}} \\left[ \\begin{matrix} 1 & 1 & 1 \\\\ 1 & 2 & 1 \\\\ 1 & 1 & 1 \\end{matrix} \\right] $$\n",
    "            2. 各点权值符合高斯分布的高斯滤波：\n",
    "                $$ {\\frac{1}{16}} \\left[ \\begin{matrix} 1 & 2 & 1 \\\\ 2 & 4 & 2 \\\\ 1 & 2 & 1 \\end{matrix} \\right] $$\n",
    "                \n",
    "        3. 中值滤波\n",
    "        \n",
    "            与前两种滤波不同，中值滤波不需要进行图像卷积计算，只需要把窗口范围内的像素值按大小排序，并取中间值作为像素的滤波值；  \n",
    "            此方法对椒盐噪声有效；\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. 简述边缘检测的基本原理，以及Sobel、LoG和Canny算子的原理差异。\n",
    "\n",
    "    1. 边缘检测的基本原理：\n",
    "        \n",
    "        边缘检测的本质是利用微分（或差分）信息，在边缘处，一次导数是极值点，二次导数是过0点；\n",
    "        \n",
    "        例如，对于图一中(a)图像，其图像函数，一阶导数，二阶导数的曲线分别如图二所示：\n",
    "        \n",
    "        图一：<img src=\"02.jpg\" width=\"400\" height=\"200\" />\n",
    "        \n",
    "        图二：<img src=\"03.jpg\" width=\"400\" height=\"400\" />\n",
    "\n",
    "        同时考虑x方向和y方向（图像坐标系），使用差分方法，采用Robert算子，其卷积核和相关模板分别为：\n",
    "        \n",
    "        1. x方向：\n",
    "        \n",
    "            卷积核：$ \\left[ \\begin{matrix} 1 & 0 \\\\ 0 & -1 \\end{matrix} \\right] $\n",
    "            \n",
    "            相关模板(卷积核旋转180度)：$ \\left[ \\begin{matrix} -1 & 0 \\\\ 0 & 1 \\end{matrix} \\right] $\n",
    "            \n",
    "            模板的右下角对应坐标(x,y), 则 $ E_x={\\frac{\\partial f(x,y)}{\\partial x}}=f(x,y)-f(x-1,y-1) $\n",
    "            \n",
    "        2. y方向：\n",
    "        \n",
    "            卷积核：$ \\left[ \\begin{matrix} 0 & 1 \\\\ -1 & 0 \\end{matrix} \\right] $\n",
    "            \n",
    "            相关模板(卷积核旋转180度)：$ \\left[ \\begin{matrix} 0 & -1 \\\\ 1 & 0 \\end{matrix} \\right] $\n",
    "        \n",
    "            模板的右下角对应坐标(x,y), 则 $ E_y={\\frac{\\partial f(x,y)}{\\partial y}}=f(x-1,y)-f(x,y-1) $\n",
    "             \n",
    "        边缘检测利用差分，属于高通滤波，其各项系数和一定为0；\n",
    "        \n",
    "    2. Sobel、LoG和Canny算子的原理差异:\n",
    "    \n",
    "        1. Sobel\n",
    "            1. x方向：\n",
    "\n",
    "                卷积核：$ \\left[ \\begin{matrix} -1 & 0 & 1 \\\\ -2 & 0 & 2 \\\\ -1 & 0 & 1 \\end{matrix} \\right] $\n",
    "\n",
    "                相关模板(卷积核旋转180度)：$ \\left[ \\begin{matrix} 1 & 0 & -1 \\\\ 2 & 0 & -2 \\\\ 1 & 0 & -1 \\end{matrix} \\right] $\n",
    "\n",
    "                模板的中心对应坐标(x,y), 则 $ {\\frac{\\partial f(x,y)}{\\partial x}}=\\left[ f(x-1,y-1)+2f(x-1,y)+f(x-1,y+1) \\right] - \\left[ f(x+1,y-1)+2f(x+1,y)+f(x+1,y+1) \\right] $\n",
    "\n",
    "            2. y方向：\n",
    "\n",
    "                卷积核：$ \\left[ \\begin{matrix} 1 & 2 & 1 \\\\ 0 & 0 & 0 \\\\ -1 & -2 & -1 \\end{matrix} \\right] $\n",
    "\n",
    "                相关模板(卷积核旋转180度)：$ \\left[ \\begin{matrix} -1 & -2 & -1 \\\\ 0 & 0 & 0 \\\\ 1 & 2 & 1 \\end{matrix} \\right] $\n",
    "\n",
    "                模板的中心对应坐标(x,y), 则 $ {\\frac{\\partial f(x,y)}{\\partial y}}=\\left[ f(x-1,y+1)+2f(x,y+1)+f(x+1,y+1) \\right] - \\left[ f(x-1,y-1)+2f(x,y-1)+f(x+1,y-1) \\right] $\n",
    "                \n",
    "        1. Laplace\n",
    "            1. 4邻域\n",
    "                卷积核（因为是中心对称算子，其相关模板与卷积核相同）：\n",
    "                $ \\left[ \\begin{matrix} 0 & 1 & 0 \\\\ 1 & -4 & 1 \\\\ 0 & 1 & 0 \\end{matrix} \\right] $\n",
    "                \n",
    "                计算公式：$ \\Delta f(x,y) = \\nabla^2 = {\\frac{\\partial^2 f}{\\partial x^2}} + {\\frac{\\partial^2 f}{\\partial y^2}} = f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1)-4f(x,y) $\n",
    "                \n",
    "            2. 8邻域\n",
    "                卷积核（因为是中心对称算子，其相关模板与卷积核相同）：\n",
    "                $ \\left[ \\begin{matrix} 1 & 1 & 1 \\\\ 1 & -8 & 1 \\\\ 1 & 1 & 1 \\end{matrix} \\right] $\n",
    "                \n",
    "                计算公式：$ \\Delta f(x,y) = \\nabla^2 = {\\frac{\\partial^2 f}{\\partial x^2}} + {\\frac{\\partial^2 f}{\\partial y^2}} = f(x-1,y-1)+f(x,y-1)+f(x+1,y-1)+f(x-1,y)+f(x+1,y)+f(x-1,y+1)+f(x,y+1)+f(x+1,y+1)-8f(x,y) $\n",
    "                \n",
    "        2. LoG\n",
    "        \n",
    "            LoG算子先对图像进行高斯滤波再用Laplace算子进行边缘检测：\n",
    "            $$ \\Delta \\left[ G_{\\sigma}(x,y) * f(x,y) \\right] = \\left[ \\Delta G_{\\sigma}(x,y) \\right] * f(x,y) = LoG * f(x,y) $$\n",
    "            从公式看出，这里先对高斯函数进行Laplace变换，得到LoG算子，然后再跟图像进行卷积运算，这样可以简化运算，提高性能；\n",
    "            常用的LoG算子取5x5的卷积核，根据σ取值不同有不同的值，常用的算子如下：\n",
    "            $$ \\left[ \\begin{matrix} -2 & -4 & -4 & -4 & -2 \\\\ -4 & 0 & 8 & 0 & -4 \\\\ -4 & 8 & 24 & 8 & -4 \\\\ -4 & 0 & 8 & 0 & -4 \\\\ -2 & -4 & -4 & -4 & -2 \\end{matrix} \\right] $$\n",
    "            \n",
    "        3. Canny\n",
    "        \n",
    "            Canny算法步骤\n",
    "            1. 平滑图像 然后 计算图像微分：平滑图像也是采用高斯滤波，然后计算微分，与LoG算子的方式类似，先对高斯函数微分，然后再与图像进行卷积运算;\n",
    "            2. 计算梯度（幅值和方向）：计算梯度幅值和方向后，对方向进行离散化，将其离散为8邻域的8个方向上，而相对的两个方向取相同的值，实际有4个方向值；\n",
    "            3. 根据梯度幅值进行非极大值抑制：得到梯度方向后，将像素与其梯度方向上的相邻的两个像素的幅值比较，如果比相邻两个像素幅值大，那么这个点就是局部极值点，也就是一个边缘点，反之则不是边缘点；这里判断为不是边缘的点将幅值设置为0，便于下一步处理；\n",
    "            4. 自动边缘连接：对梯度幅值做阈值化处理，使用两个参数$\\tau_1$和$\\tau_2$($\\tau_1<\\tau_2$)：\n",
    "                $${ \\left\\{ \\begin{array}{*{20}{l}}\n",
    "{ T_1[i,j](M(i,j)<\\tau_1) }\\\\\n",
    "{ T_2[i,j](\\tau_1 \\leq M(i,j) \\leq \\tau_2) }\\\\\n",
    "{ T_3[i,j](M(i,j) > \\tau_2) }\n",
    "\\end{array}\\right. }$$\n",
    "                得到了3个点集$T_1$、$T_2$、$T_3$：其中$T_1$中的点为假边缘，去除；$T_3$中的点位真边缘，保留；对应$T_2$中的点，如果直接或通过$T_2$中的点间接与$T_3$中的点联通，则认为是真边缘，否则认为是假边缘；\n",
    "                            \n",
    "        Sobel是一阶算子，Laplace是二阶算子，他们采用差分原理，差分可以有效的检测边缘，但会使噪声放大；LoG原理上先采用高斯滤波平滑图像去除噪声，再使用Laplace算子进行边缘检测，可以有效的抑制噪声，但同时也会使边缘变得模糊；采用一阶、二阶导数方式检测边缘会有噪声影响以及边缘模糊中断的问题；Canny算子可以将边缘自动联通，并消除虚检。\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. 简述图像直方图的基本概念，及使用大津算法进行图像分割的基本原理。\n",
    "    1. 图像直方图的基本概念：  \n",
    "        灰度直方图其横坐标是图像的灰度等级，纵坐标（直方图的高度）表示该等级像素的个数或所占百分比；  \n",
    "        如果像素点集中在低灰度区域，则图像比较暗，如果像素集中在高灰度区域，则图像比较亮；  \n",
    "        如果像素集中在某一区域，图像对比度比较低；如果像素分散在不同灰度区域，图像对比度比较高；  \n",
    "    2. 大津算法基本原理：\n",
    "        大津算法是用来确定灰度分割阈值的一种方法，最佳阈值是使背景和目标之间的差异最大的阈值，大津算法的目标是确定最佳阈值，使背景和目标之间的类间方差最大；\n",
    "        假设前景的平均灰度为$\\mu_0$，像素占比为$\\omega_0$，背景的平均灰度为$\\mu_1$，像素占比为$\\omega_1$，整幅图像的平均灰度为$\\mu$，类间方差g可以表示为：\n",
    "        $$ g={\\omega_0}{(\\mu_0 - \\mu)^2}+{\\omega_1}{(\\mu_1 - \\mu)^2} $$\n",
    "        其中：\n",
    "        $$ \\mu = {\\omega_0}\\mu_0 + {\\omega_1}\\mu_1 $$\n",
    "        代入整理得到：\n",
    "        $$ g= {\\omega_0}{\\omega_1}{(\\mu_0 - \\mu_1)^2}$$\n",
    "        通过遍历所有灰度$\\mu$，可以求得使g取最大值得$\\mu$值，即最佳分割阈值。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. 简述Harris算子对角点的定义，进行角点检测的基本原理，并说明引入角点响应函数的意义。\n",
    "    1. Harris算子对角点的定义：  \n",
    "        在图像上取一个小窗口，当向任意方向移动小窗口，小窗口内的图像灰度积分值都剧烈变化时，这个小窗口所在的位置就是角点；\n",
    "        \n",
    "    2. Harris角点检测的基本原理  \n",
    "        1. 根据角点的定义，先定义积分变化：\n",
    "        $$ E(u,v) = \\sum_{x,y}w(x,y)[I(x+u,y+v)-I(x,y)]^2 \\approx {\\left[ \\begin{matrix} u & v \\end{matrix} \\right]}{\\sum_{x,y}w(x,y) \\left[ \\begin{matrix} I^2_x & I_xI_y \\\\ I_xI_y & I^2_y \\end{matrix} \\right]}{\\left[ \\begin{matrix} u \\\\ v \\end{matrix} \\right]} $$\n",
    "        2. 上面公式E是一个二次型，可以转化为\n",
    "        $$ E = {\\left[ \\begin{matrix} u & v \\end{matrix} \\right]}{\\left[ \\begin{matrix} A & C \\\\ C & B \\end{matrix}\\right]}{\\left[ \\begin{matrix} u \\\\ v \\end{matrix} \\right]} = Au^2+Bv^2+2Cuv $$\n",
    "        3. 上述式子是一个椭圆方程，若中间的矩阵有两个特征值$\\lambda_1$和$\\lambda_2$，那么椭圆的长短轴就分别为$\\lambda_1^{-1/2}$和$\\lambda_2^{-1/2}$，根据$\\lambda_1$和$\\lambda_2$的值可以判断(x,y)是否是角点：  \n",
    "            1. $\\lambda_1$和$\\lambda_2$都比较小时，点（x,y）处于灰度变化平缓区域\n",
    "            2. 当$\\lambda_1 \\gg \\lambda_2$或$\\lambda_1 \\ll \\lambda_2$小时，点(x,y)为边界点\n",
    "            3. $\\lambda_1$和$\\lambda_2$都比较大时且近似相等时，点（x,y）为角点\n",
    "            \n",
    "    3. 角点响应函数的意义  \n",
    "        根据灰度积分变化情况判断是否角点需要预设一个阈值来判断灰度变化是否剧烈，在不同情况下很难统一，所以引入了角点响应函数：  \n",
    "        $$ R=detM-k(traceM)^2 $$\n",
    "        $$ traceM=\\lambda_1 + \\lambda_2 $$\n",
    "        $$ detM=\\lambda_1\\lambda_2 $$\n",
    "        通过角点响应函数的函数值R判断点类型：  \n",
    "        1. R接近0时，点处于灰度变化平缓区域  \n",
    "        2. R<0时，点处于边界  \n",
    "        3. R>0时，点为角点  \n",
    "        这里k为经验系数，通常取0.04 ~ 0.045"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5. 简述Hough变换的基本原理(包括参数空间变换及参数空间划分网格统计)。\n",
    "    1. Hough变换  \n",
    "        直角坐标系下的直线$y=kx+b$，原点到这条直线的距离记为$\\rho$，原点到这条直线的垂线与x轴的夹角记为$\\theta$，这条直线也可以记为$\\rho=xcos\\theta+ysin\\theta$，这样直角坐标系中的一条直线，就对应参数坐标系（极坐标系）$\\rho$$\\theta$中的一个点$(\\rho,\\theta)$；  \n",
    "        同理，直角坐标系下的一个点对应极坐标系下的一条正弦曲线：$\\rho=xcos\\theta+ysin\\theta=\\sqrt {x^2+y^2}sin(\\theta+\\psi)$  \n",
    "        直角坐标系下同一条直线上的多个点，对应的极坐标系下的多条曲线必然交于一点$(\\rho,\\theta)$\n",
    "    2. 直线检测\n",
    "        1. 将$(\\rho,\\theta)$空间量化成许多小格；  \n",
    "        2. 根据x-y平面每一个关注点（通常是边缘点）代入$\\theta$的量化值，算出各个$\\rho$，将对应格计数累加（正弦曲线离散化，将x-y坐标系下的点对应极坐标系下曲线经过的格子计数加1）；  \n",
    "        3. 当全部点变换后，对小格进行检验。设置累计阈值T，计数器大于T的小格对应于共线点，其可以用作直线拟合参数。小于T的反映非共线点，丢弃不用；（投票）  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6. 简述SIFT原理(重点是尺度空间和方向直方图原理)及ORB算子原理(重点是FAST和BRIEF)。 \n",
    "\n",
    "    1. SIFT原理\n",
    "    \n",
    "        SIFT的全称是Scale Invariant Feature Transform（尺度不变特征变换）\n",
    "        \n",
    "        SIFT算法的特点：  \n",
    "        1. 图像的局部特征，对旋转、尺度缩放、亮度变化保持不变，对视角变化、仿射变换、噪声也保持一定程度的稳定性。\n",
    "        2. 独特性好，信息量丰富，适用于海量特征库进行快速、准确的匹配。(高维特征描述子)\n",
    "        3. 多量性：即使是很少几个物体也可以产生大量的SIFT特征(不局限于角点)\n",
    "        4. 高速性：改进的SIFT匹配算法甚至可以达到实时性\n",
    "        5. 扩展性：可以很方便的与其他的特征向量进行联合。\n",
    "        \n",
    "        尺度空间：人眼可自动调节尺度，完成对物体的检测和识别；模仿人的视觉认知，把物体不同尺度下的图像都提供给机器，让机器能够对物体在不同的尺度下综合信息识别；\n",
    "        \n",
    "        抽象定义：  \n",
    "            $$ L(x,y,\\sigma) = G(x,y,\\sigma)*I(x,y) $$\n",
    "            $$ G(x,y,\\sigma) = {\\frac{1}{2 \\pi \\sigma^2}} e^{- \\frac {(x-m/2)^2+(y-n/2)^2} {2\\sigma^2} } $$\n",
    "            $\\sigma$是尺度空间因子，值越小，图像被平滑的越少，相应的尺度也就越小。大尺度对应图像的概貌特征；小尺度对应图像的细节特征。\n",
    "\n",
    "        尺度空间的建立：  \n",
    "            通过高斯函数与原图像卷积，并经过下采样，可建立原始图像的尺度空间模型（高斯金字塔）；\n",
    "\n",
    "        具体方法：构建高斯金字塔  \n",
    "            原图像，做$\\sigma$的高斯滤波后为金字塔的第0层，通过$2\\sigma$高斯滤波和降采样得到下一层；依次类推，每一次的尺度是上一层的2倍，图像的边长则是上一层的1/2；金字塔层数n取决于图像原始大小和塔顶图像大小；  \n",
    "            ![高斯金字塔1](g01.png)\n",
    "\n",
    "            因为还会把金字塔的每一层细分为不同模糊度的多张图像，所以在尺度空间中把金字塔的一层称为组（Octave），每一幅图像称为一层(Interval)；  \n",
    "            每组生成相同的图像数，称之为每组尺度数，记做S；一组内第一张图像的尺度记做$\\sigma$，这一组的第s层的尺度就是：\n",
    "            $$ \\sigma(s) = \\sigma * k^{(s-1)} $$\n",
    "            其中$ k = 2^{\\frac{1}{S}} $，$s \\in (1..S) $  \n",
    "            ![高斯金字塔2](g02.png)\n",
    "\n",
    "            为了方便计算尺度空间的极值，如果极值空间的金字塔每组层数有S，则对应的高斯金字塔的每组层数应该是S+3，为了保证极值的尺度空间连续性，而实际计算k值按S而不是S+3计算，即高斯金字塔每组在原有的基础上向更大尺度空间方向多生成了3幅图像，即这3幅图像是该组的最后三幅，而其中倒数第三幅的尺度等于下一组第一幅图像的尺度，所以下一组的第一幅图像可以由这一组的倒数第三幅图像降采样得到；\n",
    "            ![高斯金字塔3](g03.png)\n",
    "            \n",
    "        在尺度空间中求极值：  \n",
    "            先将同一组中相邻的两幅图像做差分，得到差分图像（DoG空间）：\n",
    "            ![差分图像](g04.png)\n",
    "            在差分图像中求极值，如果一个点比它周围的点（包括尺度空间相邻的图像中的邻点共26个）都大或者都小就是极值点：\n",
    "            ![尺度空间极值点](g05.png)\n",
    "  \n",
    "        关键点定位：  \n",
    "            对于上一步求得的极值点，作为候选点，根据候选点计算极值点的偏移${\\Delta}x$，以及其对比度的绝对值|D(x)|，如果${\\Delta}x$大于0.5说明关键点偏移到邻近点，取临近点作为候选点，重新继续极值点偏移，迭代计算到结果收敛，如果不收敛则去除这个点；如果|D(x)|过小也应该删除；\n",
    "            \n",
    "        消除边缘点：\n",
    "        \n",
    "        生成关键点特征描述：\n",
    "            1. 求取关键点邻域窗口内像素的梯度模值和方向\n",
    "            2. 对梯度方向离散化为8个方向\n",
    "            3. 生成方向直方图，直方图横坐标为方向，纵坐标为该方向上梯度模值得加权和\n",
    "            4. 找到方向直方图中最大的方向为主方向，如果还有方向的值大于主方向的80%，这个方向为辅方向；\n",
    "            5. 关键点描述：\n",
    "                1. 坐标轴旋转为关键点的主方向\n",
    "                2. 通过坐标变换，重新生成领域窗口内的像素图像\n",
    "                3. 在新的坐标系下重新计算梯度和方向，\n",
    "                4. 进行高斯加权运算\n",
    "                5. 将领域窗口划分为4x4的小窗口，每个窗口分别计算8个方向的梯度信息（直方图），最后取4x4个小窗口，得到4 * 4 * 8=128维向量\n",
    "                6. 归一化处理（消除缩放影响）\n",
    "                7. 排除光照影响，将归一化的结果在0.2处截断（li > 0.2 ? 0.2 : li）\n",
    "            \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "6. 简述SIFT原理(重点是尺度空间和方向直方图原理)及ORB算子原理(重点是FAST和BRIEF)。 \n",
    "\n",
    "    2. ORB算子原理\n",
    "\n",
    "        ORB = oFAST + rBRIEF  \n",
    "        oFAST负责特征点提取  \n",
    "        rBRIEF负责特征点描述  \n",
    "    \n",
    "        1. oFAST\n",
    "        \n",
    "            1. FAST特征检测  \n",
    "                ![FAST算法](ORB01.png)  \n",
    "                图像中的一点P，以P为圆心，画半径为3像素的圆，圆周共经过16个点，如果圆周上有N个连续像素的灰度都比P点大或比P点小，就认为P点是特征点；根据N的取值，可以称为FAST-N，常用的是FAST-9和FAST-12；  \n",
    "                快速排除非特征点：去上下左右4个方向点1、5、9、13先排查，至少有3个像素灰度都大于或者都小于P点的灰度才可能是特征点，否则排除此点；\n",
    "\n",
    "            2. 使用机器学习的方法筛选最优特征点  \n",
    "                对于一些已知特征点的图像，将特征点周围的16个像素按灰度归为三个集合，较暗的$P_d$，相近的$P_s$，较亮的$P_b$（依据灰度与特征点灰度距离与预定值t比较判断）  \n",
    "                使用$K_p$定义特征点是否角点  \n",
    "                使用上述数据，利用ID3算法训练一个决策树，这个决策树可以用于其他图像的检测  \n",
    "\n",
    "            3. 使用非极大值抑制方法排除临近位置的多个特征点  \n",
    "                一个特征点p的领域中没有其他特征点，则保留；  \n",
    "                在一个特征点p的邻域中还有其他特征点，计算每个特征点的FAST得分值s，如果p的FAST得分最大，则保留，否则删除；  \n",
    "                得分值计算公式（注意不是所有16个点都计算灰度差值的绝对值，也不是所有绝对值的和）  \n",
    "                $$ s = max \\left\\{ \\begin{array}{*{20}{l}} {\\Sigma(pixel values - p) if (value - p) > t } \\\\ {\\Sigma(p - pixel values) if (p - value) > t } \\end{array} \\right. $$\n",
    "\n",
    "            4. 尺度空间处理  \n",
    "                使用一个比例因子（opencv默认为1.2）按比例将原始图像逐层缩小，构建一个总共有n层（opencv默认为8层）的图像金字塔；  \n",
    "                将n层图像都提按前述方法取特征点，这些特征点的合集作为这个图像的oFAST特征点；\n",
    "\n",
    "            5. 旋转不变性  \n",
    "                计算各特征点的方向：以特征点为中心画半径为r的圆，特征点到该圆的质心的方向作为该特征点的方向\n",
    "            \n",
    "        2. rBRIEF\n",
    "        \n",
    "            1. BRIEF  \n",
    "                对应oFAST检测到的特征点P，以P为圆心，d为半径做圆O，在圆内按某种方式选n对点，每一对像素(p,q)进行比较，如果$I_p > I_q$，记做1，否则记做0，这样可以得到n位的特征描述子；\n",
    "                \n",
    "            2. 消除旋转影响  \n",
    "                对BRIEF算法中选出的点对，根据oFAST输出的特征点方向进行旋转，将x轴方向旋转到与特征点方向相同；然后再计算点对的特征值（**为什么不先旋转坐标再选点呢？**）  \n",
    "                \n",
    "            3. 相关性优化  \n",
    "                使用300k个特征点的数据集用于学习，选取点对改成在31x31的邻域内选5x5的小区域对，每个小区域的灰度均值作为这个小区域的值来生成描述子，总共有265356种选法，所有这些选法都用来生成描述子；  \n",
    "                每个特征点描述子的二进制值作为1行，形成总共300k行，265356列的矩阵；  \n",
    "                对矩阵每一列计算平均值，并按列均值到0.5的距离重新排序；  \n",
    "                从第一列开始，选取相关性最小的256列；这256对的小区域中心点位置就是学习到的相关性最小的点对选取方法；处理图像时用这些点对生成RBRIEF特征描述；\n",
    "                "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "附1：高斯模板说明：\n",
    "\n",
    "二维模板大小为m * n(通常我们使用n * n 的模板)，则模板上的元素(x, y)对应的高斯计算公式为：\n",
    "$$ G(x,y) = {\\frac{1}{2 \\pi \\sigma^2}} e^{- \\frac {(x-m/2)^2+(y-n/2)^2} {2\\sigma^2} } $$\n",
    "其中，σ是正态分布的标准差，σ值越大，图像越模糊(平滑)。r为模糊半径，模糊半径是指模板元素到模板中心的距离。 \n",
    "高斯模板是中心对称的。  \n",
    "通常r取2.5到3倍σ，大概3σ距离之外的像素都可以看作不起作用，这些像素的计算也就可以忽略。图像处理程序只需要计算（6σ+1）×（6σ+1）的矩阵就可以保证相关像素影响。  \n",
    "为了使滤波后的图像与原图像等大，需要对原图像进行扩展，使用半径为r模板时，对m * n的图像来说，扩展后的大小为(m+2r) * (n+2r)  \n",
    "当图片变大时，高斯模板(高斯核)和卷积运算量将大幅度提高。根据高斯函数的可分离性，可对二维高斯模糊函数进行改进  \n",
    "$$ G(x,y) = {\\frac{1}{2 \\pi \\sigma^2}} e^{- \\frac {(x-m/2)^2+(y-n/2)^2} {2\\sigma^2} } = {\\frac{1}{2 \\pi \\sigma^2} } e^{- \\frac {(x-m/2)^2} {2\\sigma^2} } e^{- \\frac {(y-n/2)^2} {2\\sigma^2} }  $$\n",
    "这样可以将二维变换拆解成两个一维变换，可以大大减少运输量；"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
